package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/24
 * @description <a href="https://leetcode.cn/problems/delete-node-in-a-bst/description/">...</a>
 */
public class Leetcode450_删除二叉搜索树中的节点 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法实现
     * 首先利用二叉搜索树的性质,根据节点值的大小,找到待删除的节点
     * 待删除的节点root分为以下几种情况:
     * -root为叶子节点,没有子树。此时可以直接将它删除,即返回空。
     * -root只有左子树,没有右子树。此时可以将它的左子树作为新的子树,返回它的左子节点
     * -root只有右子树,没有左子树。此时可以将它的右子树作为新的子树,返回它的右子节点
     * -root既有左子树,也有右子树。这时可以将root的后继节点(比root大的最小节点,即它的右子树中的最小节点)作为新的根节点替代root,并在右子树中删除后继节点
     * <p>
     * 时间复杂度O(N) 需要遍历一次树
     * 空间复杂度O(logN) 递归栈深度
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        //递归终止条件
        if (root == null) {
            return null;
        }

        //利用二叉搜索树的性质,找到值为key的节点
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }

        //找到了目标节点,进行删除操作
        if (root.left == null && root.right == null) {   //root为叶子节点,没有子树。此时可以直接将它删除,即返回空。
            return null;
        }

        if (root.right == null) { //root只有左子树,没有右子树。此时可以将它的左子树作为新的子树,返回它的左子节点
            return root.left;
        }
        if (root.left == null) { //root只有右子树,没有左子树。此时可以将它的右子树作为新的子树,返回它的右子节点
            return root.right;
        }

        //root既有左子树,也有右子树,找到root的后继节点successor
        TreeNode successor = root.right;
        while (successor.left != null) {
            successor = successor.left;
        }

        //在root的右子树中删除successor
        root.right = deleteNode(root.right, successor.val);

        //使用successor替代root节点并返回
        successor.left = root.left;
        successor.right = root.right;


        return successor;
    }


}
